package codetop.microsoft.T236;

import util.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: 18362
 * @Create: 2022-08-12 23:01:08 星期五
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        tranverse(root, null, map);
        Set<TreeNode> set = new HashSet<>();
        TreeNode head = p;
        while (head != null) {
            set.add(head);
            head = map.get(head);
        }
        head = q;
        while (!set.contains(head))
            head = map.get(head);
        return head;
    }

    private void tranverse(TreeNode root, TreeNode parent, Map<TreeNode, TreeNode> map) {
        if (root == null)
            return;
        map.put(root, parent);
        tranverse(root.left, root, map);
        tranverse(root.right, root, map);
    }
}
